#include "stack.h"
#include <string>

/*
 * 判断输入字符串是否为回文
 *
 * 算法分析：由于栈先进后出，所以通过一个栈很难判断头尾数值大小，
 * 故引用另外一个栈，折半压入原栈的元素，然后对栈顶逐个比较
 *
 * @param S  Stack 类型
 */

bool isHuiWen(Stack S){
    
    int n = S.getSize()/2;     //取栈的前一半长度
    bool  isOdds = S.getSize() &1;   //判断是否奇偶数
    int i =0;
    char e1,e2;
    bool flag = true;

    Stack *S2;
    S2 = new Stack(n);
    while(i<n){   //将原栈的一半数据压入栈2中
        S2->push(S.pop());
        i++;
    }

    //如果S的元素个数是奇数，去掉S多余的一个元素
    if(isOdds) {
        e1 = S.pop();
    }
    
    //比较两个栈是否相等
    i=0;
    while(i<n){
        if(S.pop() != S2->pop()){
            flag = false;
        }
        i++;
    }
 
    return flag;
}


int main()
{

    string str;
    cout << "请输入任意字符串，回车表示结束.\n";
    getline(cin, str);
    cout << "输入的字符串是："<<str<<"\n";

    //压入栈中
    int length, n =0 ;
    char a;
    Stack *stack_1;

    length = str.length();

    //初始化栈
    stack_1 = new Stack(length);
    //压入栈中
    while(length >0){
        stack_1->push(str[n]);
        n++;
        length--;
    }

    //输出栈的值
    stack_1->output();

    //判断是否回文
    bool result;
    result = isHuiWen(*stack_1);

    if(result){
        cout <<"是回文";
    }else{
        cout <<"不是回文";
    }

}

